package com.smh;

import com.smh.interfaces.Priority;
import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author shiminghui
 * @date 2025/2/19 17:49
 * @description: TODO
 */
public class _029_堆_heapify {


    @Test
    public void test1() {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.add(1);
        maxHeap.add(2);
        maxHeap.add(3);
        maxHeap.add(4);
        maxHeap.add(5);
        maxHeap.heapify(); // 调整堆
//        while (!maxHeap.isEmpty()) {
//            System.out.println(maxHeap.poll());
//        }
        maxHeap.sort();

    }

    @Test
    public void test2() {
        int[] ints = {1, 2, 3, 4, 5, 6};
        MinHeap minHeap = new MinHeap(3);
        for (int i = 0; i < ints.length; i++) {
            if (i < 3) {
                minHeap.offer(ints[i]);
            } else if (minHeap.peek() < ints[i]) {
                minHeap.replace(ints[i]);
            }
        }
        System.out.println(minHeap.peek());
    }

    /**
     * 第K个最大元素
     *
     * @param nums 数组
     * @param k    第k个最大元素
     * @return 第k个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        /*MinHeap minHeap = new MinHeap(k);
        for (int i = 0; i < nums.length; i++) {
            if (i < k){
                minHeap.offer(nums[i]);
            }else {
                minHeap.replace(nums[i]);
            }
        }
        return minHeap.peek();*/
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
                new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return Integer.compare(o1, o2);
                    }
                }
        );
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                priorityQueue.offer(nums[i]);
            } else if (nums[i] > priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(nums[i]);
            }
        }
        System.out.println(priorityQueue.peek());
        return priorityQueue.peek();
    }

    private static class MaxHeap {
        private int[] data;
        private int size;
        private int capacity;

        public MaxHeap(int capacity) {
            this.capacity = capacity;
            this.data = new int[capacity];
        }

        public MaxHeap(int[] data) {
            this.data = data;
            this.size = data.length;
            this.capacity = data.length;
            this.heapify();
        }

        public MaxHeap() {
            this(10);
        }

        /**
         * 调整堆
         */
        public void heapify() {
            // 找到最后一个非叶子节点
            int parent = (size - 1) / 2;
            // 从最后一个非叶子节点开始调整
            for (int i = parent; i >= 0; i--) {
                down(i);
            }
        }

        // 下潜
        private void down(int index) {
            // 找到当前节点的左右子节点
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int max = index;
            if (left < size && data[left] > data[max]) {
                max = left;
            }
            if (right < size && data[right] > data[max]) {
                max = right;
            }
            if (max != index) { // 如果当前节点不是最大值,则交换位置
                int temp = data[index];
                data[index] = data[max];
                data[max] = temp;
                down(max); // 继续向下调整
            }
        }

        // 上浮
        private void up(int index) {
            if (index == 0) {
                return;
            }
            int parent = (index - 1) / 2;
            if (data[parent] < data[index]) {
                int temp = data[parent];
                data[parent] = data[index];
                data[index] = temp;
                up(parent);
            }
        }

        /**
         * 添加元素
         *
         * @param value 值
         * @return true:添加成功 false:添加失败
         */
        public boolean offer(int value) {
            if (isFull()) {
                return false;
            }
            data[size] = value;
            up(size);
            size++;
            return true;
        }

        /**
         * 在堆尾部中添加元素
         *
         * @param value 值
         * @return true:添加成功 false:添加失败
         */
        public boolean add(int value) {
            if (isFull()) {
                return false;
            }
            data[size] = value;
            size++;
            return true;
        }

        /**
         * 删除堆顶元素
         *
         * @return 堆顶元素
         */
        public int poll() {
            if (isEmpty()) {
                return -1;
            }
            int temp = data[0];
            data[0] = data[size - 1];
            size--;
            down(0);
            return temp;
        }

        /**
         * 删除指定位置的元素
         *
         * @param index 索引
         * @return 删除的元素
         */
        public int poll(int index) {
            if (isEmpty()) {
                return -1;
            }
            if (index < 0 || index >= size) {
                return -1;
            }
            int temp = data[index];
            data[index] = data[size - 1];
            size--;
            down(index);
            return temp;
        }

        /**
         * 获取堆顶元素
         *
         * @return 堆顶元素
         */
        public int peek() {
            if (isEmpty()) {
                return -1;
            }
            return data[0];
        }

        /**
         * 替换堆顶元素
         *
         * @param value 值
         * @return true:替换成功 false:替换失败
         */
        public boolean replace(int value) {
            if (isEmpty()) {
                return false;
            }
            data[0] = value;
            down(0);
            return true;
        }

        /**
         * 堆排序
         */
        public void sort() {
            int count = size;
            while (!isEmpty()) {
                int temp = data[0];
                data[0] = data[size - 1];
                data[size - 1] = temp;
                size--;
                down(0);
            }
            size = count;
            for (int i = 0; i < size; i++) {
                System.out.println(data[i]);
            }
        }

        public boolean isEmpty() {

            return size == 0;
        }

        public boolean isFull() {

            return size == capacity;
        }


    }

    private static class MinHeap {
        private int[] data;
        private int size;
        private int capacity;

        public MinHeap(int capacity) {
            this.capacity = capacity;
            this.data = new int[capacity];
        }

        public MinHeap(int[] data) {
            this.data = data;
            this.size = data.length;
            this.capacity = data.length;
            this.heapify();
        }

        public MinHeap() {
            this(10);
        }

        /**
         * 调整堆
         */
        public void heapify() {
            // 找到最后一个非叶子节点
            int parent = (size - 1) / 2;
            // 从最后一个非叶子节点开始调整
            for (int i = parent; i >= 0; i--) {
                down(i);
            }
        }

        // 下潜
        private void down(int index) {
            // 找到当前节点的左右子节点
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int max = index;
            if (left < size && data[left] < data[max]) {
                max = left;
            }
            if (right < size && data[right] < data[max]) {
                max = right;
            }
            if (max != index) { // 如果当前节点不是最大值,则交换位置
                int temp = data[index];
                data[index] = data[max];
                data[max] = temp;
                down(max); // 继续向下调整
            }
        }

        // 上浮
        private void up(int index) {
            if (index == 0) {
                return;
            }
            int parent = (index - 1) / 2;
            if (data[parent] > data[index]) {
                int temp = data[parent];
                data[parent] = data[index];
                data[index] = temp;
                up(parent);
            }
        }

        /**
         * 添加元素
         *
         * @param value 值
         * @return true:添加成功 false:添加失败
         */
        public boolean offer(int value) {
            if (isFull()) {
                return false;
            }
            data[size] = value;
            up(size);
            size++;
            return true;
        }

        /**
         * 在堆尾部中添加元素
         *
         * @param value 值
         * @return true:添加成功 false:添加失败
         */
        public boolean add(int value) {
            if (isFull()) {
                return false;
            }
            data[size] = value;
            size++;
            return true;
        }

        /**
         * 删除堆顶元素
         *
         * @return 堆顶元素
         */
        public int poll() {
            if (isEmpty()) {
                return -1;
            }
            int temp = data[0];
            data[0] = data[size - 1];
            size--;
            down(0);
            return temp;
        }

        /**
         * 删除指定位置的元素
         *
         * @param index 索引
         * @return 删除的元素
         */
        public int poll(int index) {
            if (isEmpty()) {
                return -1;
            }
            if (index < 0 || index >= size) {
                return -1;
            }
            int temp = data[index];
            data[index] = data[size - 1];
            size--;
            down(index);
            return temp;
        }

        /**
         * 获取堆顶元素
         *
         * @return 堆顶元素
         */
        public int peek() {
            if (isEmpty()) {
                return -1;
            }
            return data[0];
        }

        /**
         * 替换堆顶元素
         *
         * @param value 值
         * @return true:替换成功 false:替换失败
         */
        public boolean replace(int value) {
            if (isEmpty()) {
                return false;
            }
            data[0] = value;
            down(0);
            return true;
        }

        /**
         * 堆排序
         */
        public void sort() {
            int count = size;
            while (!isEmpty()) {
                int temp = data[0];
                data[0] = data[size - 1];
                data[size - 1] = temp;
                size--;
                down(0);
            }
            size = count;
            for (int i = 0; i < size; i++) {
                System.out.println(data[i]);
            }
        }

        public boolean isEmpty() {

            return size == 0;
        }

        public boolean isFull() {

            return size == capacity;
        }


    }

}
